﻿using System;
using System.Collections.Generic;

namespace ProblemsSet
{
    public class Problem_93 : BaseProblem
    {
        public override object GetResult()
        {
            long total = 0;
            string totres = "";
            for (var a = 1; a <= 6; a++)
            {
                for (var b = a+1; b <= 7; b++)
                {
                    for (var c = b+1; c <= 8; c++)
                    {
                        for (var d = c+1; d<=9;d++)
                        {
                            var digits = new List<double>() { a, b, c, d };
                            var res = new List<long>();
                            CountPolsk(ref res, digits);
                            res.Sort();

                            long rs = 1;
                            if (res[0] != 1) break;
                            for (var i = 1; i < res.Count; i++)
                            {
                                if (res[i] == res[i-1]+1)
                                {
                                    rs++;
                                }
                                else
                                {
                                    break;
                                }
                            }
                            if (rs > total)
                            {
                                total = rs;
                                totres = a.ToString() + b.ToString() + c.ToString() + d.ToString();
                            }
                        }
                    }
                }
            }

            return totres;
        }

        private static void CountPolsk(ref List<long> result, IList<double> values)
        {
            if (values.Count == 0) return;
            if (values.Count == 1)
            {
                if (values[0] == 0) return;
                if (Math.Truncate(values[0]) == values[0])
                {
                    var tmp = (long) values[0];
                    if (tmp < 0) tmp = -tmp;
                    if (result.Contains(tmp)) return;
                    result.Add(tmp);
                }
                return;
            }
            for (var i = 0; i < values.Count-1; i++)
            {
                for (var j = i + 1; j < values.Count; j++)
                {
                    var hs = new HashSet<double>();
                    var tmp = new List<double>(values);
                    var a1 = values[i];
                    var a2 = values[j];
                    tmp.RemoveAt(j);
                    tmp.RemoveAt(i);

                    double q = a1 + a2;
                    var tmp2 = new List<double>(tmp) {q};
                    if (!hs.Contains(q))
                    {
                        hs.Add(q);
                        CountPolsk(ref result, tmp2);
                    }

                    q = a1 - a2;
                    tmp2 = new List<double>(tmp) {q};
                    if (!hs.Contains(q))
                    {
                        hs.Add(q);
                        CountPolsk(ref result, tmp2);
                    }

                    q = a2 - a1;
                    tmp2 = new List<double>(tmp) { q };
                    if (!hs.Contains(q))
                    {
                        hs.Add(q);
                        CountPolsk(ref result, tmp2);
                    }

                    q = a1 * a2;
                    tmp2 = new List<double>(tmp) { q };
                    if (!hs.Contains(q))
                    {
                        hs.Add(q);
                        CountPolsk(ref result, tmp2);
                    }

                    if (a2 != 0)
                    {
                        q = a1/a2;
                        tmp2 = new List<double>(tmp) {q};
                        if (!hs.Contains(q))
                        {
                            hs.Add(q);
                            CountPolsk(ref result, tmp2);
                        }
                    }

                    if (a1 != 0)
                    {
                        q = a2/a1;
                        tmp2 = new List<double>(tmp) {q};
                        if (!hs.Contains(q))
                        {
                            hs.Add(q);
                            CountPolsk(ref result, tmp2);
                        }
                    }

                }
            }
        }

        public override string Problem
        {
            get
            {
                return @"By using each of the digits from the set, {1, 2, 3, 4}, exactly once, and making use of the four arithmetic operations (+, , *, /) and brackets/parentheses, it is possible to form different positive integer targets.

For example,

8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3)  1
36 = 3 * 4 * (2 + 1)

Note that concatenations of the digits, like 12 + 34, are not allowed.

Using the set, {1, 2, 3, 4}, it is possible to obtain thirty-one different target numbers of which 36 is the maximum, and each of the numbers 1 to 28 can be obtained before encountering the first non-expressible number.

Find the set of four distinct digits, a  b < c  d, for which the longest set of consecutive positive integers, 1 to n, can be obtained, giving your answer as a string: abcd.";
            }
        }

        public override bool IsSolved
        {
            get
            {
                return true;
            }
        }

        public override object Answer
        {
            get
            {
                return "1258";
            }
        }

    }
}
